package com.nowcoder.code.hjnc;

import java.util.Arrays;

public class NC91 {

    public int[] LIS(int[] arr) {
        lengthOfLIS(arr);
        int[] ans = new int[len];
        return ans;
    }

    int[] dp;
    int len;
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) return 0;
        dp = new int[nums.length + 1];
        dp[0] = nums[0];
         len = 0;
        for (int i : nums) {
            if (i > dp[len]) {
                len++;
                dp[len] = i;
            } else {
                int start = 0;
                int end = len;
                int mid = (start + end) >> 1;
                while (start <= end) {
                    if (dp[mid] == i) {
                        break;
                    } else if (dp[mid] > i) {
                        end = mid - 1;
                    } else {
                        start = start + 1;
                    }
                    mid = (start + end) >> 1;
                }

                if (mid < 0) {
                    dp[0] = i;
                } else if (dp[mid] != i) {
                    dp[mid + 1] = i;
                }

            }


        }

        return len + 1;

    }

    public static void main(String[] args) {
        int[] is = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println(Arrays.toString(new NC91().LIS(is)));

    }

}
